package com.example.arithmeticleetcode.arithmetic;

/**
 * @program: arithmetic-leetcode
 * @description: 选择排序 稳定的排序，复杂度O(n^2)
 * @author: FangZhen
 * @create: 2020-04-15 11:02
 **/
public class ChoicSort {

    public static void main(String[] args) {
        int[] arr = {1, 9, 5, 6, 3};
        choiceSortTest01(arr);
    }

    /**
     * 选择排序的精髓，就是指定一个最大值，总共循环数组的长度次数，在最外层循环的时候，最里面这一层是选择出这个里面最大的数
     * 然后将这个数，移到最右边，每次只能找一个，所以内侧循环每次减一，找到这个想要的数据角标在进行和内侧循环最后一个
     * 角标互换数据
     *
     * @param arr
     */
    public static void choiceSortTest01(int[] arr) {
        int temp, pos;
        for (int i = 0, len = arr.length; i < len; i++) {
            pos = 0;
            for (int j = 0; j < len - i; j++) {
                if (arr[j] > arr[pos]) {
                    pos = j;
                }
            }

            temp = arr[pos];
            arr[pos] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }

        for (int i : arr) {
            System.out.println(i);
        }
    }
}
